def greedy_search(vertices, independent_set)
  return independent_set if vertices.empty?

  max_num_of_adjoinable_vertices = -1
  selected_vertex_index = -1

  i=0
  vertices.each { |v|
    num_adjoinable_vertices = vertices.size - (vertices & v.adjList).size - 1

    if num_adjoinable_vertices > max_num_of_adjoinable_vertices
    max_num_of_adjoinable_vertices = num_adjoinable_vertices
    selected_vertex_index = i
    end

    i+=1
  }

  v = vertices[selected_vertex_index]
  independent_set << v
  vertices.delete_at(selected_vertex_index)
  v.adjList.each { |u|
    vertices.delete(u)
  }

  return greedy_search(vertices, independent_set)

end

def compute_formula(g)
  n = g.vertices.length
  m = 0
  g.vertices.each { |v|
  #get degree of v
    degree = v.adjList.length
    m = degree if degree > m
  }
  min_set_size = ( n / (m+1.0) ).ceil

  return min_set_size
end

def remove_adjVertices(vertices, v)
  v.adjList.each { |w|
    vertices.delete(w)
  }
end

# Q4 - this method will only be invoked AFTER Q3(a) and Q3(b) have been tested on the submission server

def get_largest_set_of_independent_actors(g)

  time = Time.now

  min_set_size = compute_formula(g)

  result = []
  result_sets = []

  g.vertices.each { |v|
    result = [v]

    vertices_copy = g.vertices.clone
    remove_adjVertices(vertices_copy, v)
    vertices_copy.delete(v)

    result = greedy_search(vertices_copy, result)
    result_sets << result if result.length >= min_set_size

    break if result_sets.size >=

  }

  optimal_result = []
  result_sets.each { |x|
    optimal_result = x if x.length > optimal_result.length
  }

  puts "Execution: #{Time.now - time} s"
  puts "Quality: #{optimal_result.size}"

  return optimal_result

end

#-------------------------------------------------------------------
